This section is intended to provide a background or context to the invention that is recited in the claims. The description herein may include concepts that could be pursued, but are not necessarily ones that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, what is described in this section is not prior art to the description and claims in this application and is not admitted to be prior art by inclusion in this section.
A distributed data storage is a computer system where information or data is stored on more than one node. The data is often automatically replicated or duplicated over a large number of servers or nodes that are either located in the same physical location or distributed over the computer network. For example website servers have to be globally distributed for low latency and failover. Further, current applications require processing of huge amounts of data, which is achieved by distributed processing. Thus, the data may also be automatically partitioned so that the server contains only a subset of the total data. The replication and distribution of data over several nodes improves, inter alia, availability of the data.
In many solutions the same data set is shared between several applications. Each application may have different requirements on characteristics of the data storage. Some requirements may not be possible to fulfill at the same time by the same data storage. Some requirements may be contradictory, override or influence each other.
For example, according to the CAP theorem, also known as Brewer's theorem, it is impossible for a distributed system to simultaneously provide all three of the following requirements: consistency, availability and partition tolerance. It means that maximum two of the three requirements can be fulfilled by the same data storage.
In this context, consistency means that all nodes see the same data at the same time, i.e., the same data item has the same value when read from different replicas. Thus, a system is consistent if an update is applied to all relevant nodes at the same logical time. Availability means that every request received by a non-failing node in the system must result in a response. In other words, availability means that data can always be read from and written to a node, i.e., the system is continuously available. Partition tolerance means that a cluster can survive communication breakages that separate the cluster into multiple partitions unable to communicate with each other. Partition tolerant system thus works well across physical network partitions, i.e., the system continues to operate despite arbitrary message loss or failure of part of the system, e.g., if the network stops delivering messages between two sets of servers. In other words, the system is partition tolerant if processing can continue in all partitions in the case of a network failure causing partitioning.
In a system that may suffer partitions, as distributed systems do, the trade-off is between consistency and availability. If there is a partition in the network, either consistency or availability is lost. Either the system responds to all requests, potentially returning outdated reads and accepting conflicting writes (i.e., consistency is lost), or it refuses to respond to some requests to preserve data consistency (i.e., availability is lost).
Consistency can be improved by getting more nodes involved in the interaction, i.e. more interaction between the nodes is required for each write/update to guarantee that data is consistent in all nodes before response, which in turn increases latency (a response time). Another trade-off is thus between consistency and latency. In a consistent system all nodes need to be updated synchronously, which involves high latency. In case of asynchronous updates latency is low but data could be inconsistent between nodes. Also availability can be seen as a limit of tolerable latency; once latency is too high, data is regarded as unavailable.
In many instances, improving one requirement influences other requirements negatively. For example, inconsistencies can be reduced at the expense of availability and performance. Improving consistency may also have negative impact on multiple client support and horizontal scalability (that corresponds to partition tolerance). Improving availability or concurrency control (coordinating concurrent accesses to a data storage) and horizontal scalability in turn increases latency.
As a further example of contradictory or conflicting data storage requirements one can consider Fast Read versus Fast Write. It is assumed that it is not possible to adjust data storages for both Fast Read and Fast Write at the same time but it is necessary to choose either one of them or tune a data storage for values between Fast Read and Fast Write (i.e. medium Fast Read and medium Fast Write). More examples of conflicting data storage requirements will become evident in the detailed description of the drawings.